/*
 * 0633. 寻找重复的数
 * 给出一个数组 nums 包含 n + 1 个整数，每个整数是从 1 到 n (包括边界)，保证至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
 * https://www.lintcode.com/problem/find-the-duplicate-number/description
 * 
 * 样例
 * 给出 nums = [5,5,4,3,2,1]，返回 5.
 * 给出 nums = [5,4,4,3,2,1]，返回 4.
 * 
 * 2018.06.22 @jeyming
 */
package find_the_duplicate_number_0633;

import java.util.Arrays;

public class Find_the_duplicate_number_0633 {
	 /**
     * @param nums: an array containing n + 1 integers which is between 1 and n
     * @return: the duplicate one
     */
    public static int findDuplicate(int[] nums) {
        // write your code here
    	Arrays.sort(nums, 0, nums.length);
    	for(int i = 1; i < nums.length; ++i) {
    		if(nums[i - 1] == nums[i])
    			return nums[i];
    	}
    	return 0;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int nums[] = {5,5,4,3,2,1};
		System.out.println(findDuplicate(nums));

	}

}
